package easy;

import java.util.*;

/**
 * @author lzy
 * @version v1.0
 * Create DateTime: 2019/2/26 18:22
 * <p>
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
 * <p>
 * 有效字符串需满足：
 * <p>
 * 左括号必须用相同类型的右括号闭合。
 * 左括号必须以正确的顺序闭合。
 * 注意空字符串可被认为是有效字符串。
 */
public class ValidParenthesis {
    public static void main(String[] args) {
        Solution solution = new ValidParenthesis().new Solution();
//        String str = "(([]){})";
//        String str = "(][(}(])(({]{{){){(]}}}){}))(){(}[{)})[[";
//        String str = "{{)}";
//        String str = "[{()}]";
        String str = "[(){}[]({})]";
        System.out.println(solution.isValid(str));
    }

    private class Solution {
        public boolean isValid(String s) {
            // 字符为奇数个字符直接返回false
            if (s.length() % 2 == 1) {
                return false;
            }

            //空字符串是有效字符串
            if (s == null || s.trim() == "") {
                return true;
            }

            // 转为数组处理
            char[] chars = s.toCharArray();
            if (chars.length == 0) {
                return true;
            }
            // 如果直接就是以反方向括号开头的，则直接返回false
            if (isRightParenthesis(chars[0])) {
                return false;
            }

            // 先切分，然后判断，然后继续切分

            List<Character> characters = new ArrayList<>();
            for (char aChar : chars) {
                characters.add(aChar);
            }
            return deduce(characters);

        }

        // 对单独的一段进行切分
        private boolean deduce(List<Character> chars) {
            if (isRightParenthesis(chars.get(0))) {
                return false;
            }
            List<List<Character>> subList = cutArray(chars);
            for (List<Character> list : subList) {
                if (!isArrayBalance(list)) {
                    return false;
                } else {
                    if (list.size() > 2) {
                        List<Character> temp = list.subList(1, list.size() - 1);
                        if (!deduce(temp)) {
                            return false;
                        }
                    }
                }
            }
            return true;
        }

        // 切分子串并返回子串长度:左右括号数目相等
        private List<List<Character>> cutArray(List<Character> chars) {
            // 切分子串进行处理
            List<List<Character>> result = new ArrayList<>();
            Map<Character, Integer> countMap = new HashMap<>();
            countMap.put('(', 0);
            countMap.put('[', 0);
            countMap.put('{', 0);

            List<Character> list = new ArrayList<>();
            for (Character aChar : chars) {
                list.add(aChar);
                // 如果是左括号，加1，如果是右括号，减1
                if (isLeftParenthesis(aChar)) {
                    int count = countMap.get(aChar) + 1;
                    countMap.put(aChar, count);
                } else {
                    aChar = getLeftByRight(aChar);
                    int count = countMap.get(aChar) - 1;
                    countMap.put(aChar, count);
                }

                if (canStop(countMap)) {
                    result.add(list);
                    list = new ArrayList<>();
                }
            }
            if (result.isEmpty()) {
                result.add(chars);
            }

            return result;
        }

        // 如果有所计数都为0，则判断可以切分
        private boolean canStop(Map<Character, Integer> countMap) {
            for (Integer value : countMap.values()) {
                if (value != 0) {
                    return false;
                }
            }
            return true;
        }

        // 判断子串是否平衡
        private boolean isArrayBalance(List<Character> chars) {
            if (isRightParenthesis(chars.get(0))) {
                return false;
            }
            //第一个和最后一个必须是配对的
            if (getRightByLeft(chars.get(0)) == chars.get(chars.size() - 1)) {
                return true;
            }
            return false;
        }

        // 是否是右括号
        private boolean isRightParenthesis(char c) {
            if (c == ')' || c == ']' || c == '}') {
                return true;
            }
            return false;
        }

        // 是否是左括号
        private boolean isLeftParenthesis(char c) {
            if (c == '(' || c == '[' || c == '{') {
                return true;
            }
            return false;
        }

        //通过左括号找对应的右括号
        private char getRightByLeft(char c) {
            Map<Character, Character> map = new HashMap<>();
            map.put('(', ')');
            map.put('[', ']');
            map.put('{', '}');
            return map.get(c);
        }

        //通过右括号找对应的左括号
        private char getLeftByRight(char c) {
            Map<Character, Character> map = new HashMap<>();
            map.put(')', '(');
            map.put(']', '[');
            map.put('}', '{');
            return map.get(c);
        }
    }

    // 这个题目需要使用stack解决
    private class Solution2 {
        public boolean isValid(String s) {
            if (s == null || s.trim().length() == 0) {
                return true;
            }
            if (s.length() % 2 == 1) {
                return false;
            }
            if (s.startsWith(")") || s.startsWith("]") || s.startsWith("}")) {
                return false;
            }

            LinkedList<Character> stack = new LinkedList<>();
            for (char c : s.toCharArray()) {
                if (c == '(' || c == '[' || c == '{') {
                    stack.push(c);
                } else {
                    if (getLeftByRight(c) != stack.pop()) {
                        return false;
                    }
                }
            }

            return stack.isEmpty();
        }

        //通过右括号找对应的左括号
        private char getLeftByRight(char c) {
            Map<Character, Character> map = new HashMap<>();
            map.put(')', '(');
            map.put(']', '[');
            map.put('}', '{');
            return map.get(c);
        }
    }
}
